package com.faiz.algorithm;

public class SortList {
    public ListNode sortList(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
        return sortList(head, tail);
    }

    //思路：使用自顶向下的归并排序
    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null && tail != null) {
            return null;
        }
        if (head == tail) {
            return head;
        }
        //临时链表头
        ListNode tmp = new ListNode(0);
        tmp.next = head;
        ListNode slow = tmp, fast = tmp;
        while (fast != tail) {
            fast = fast.next;
            slow = slow.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        //slow就是链表的中点
        ListNode l1 = sortList(head, slow);
        ListNode l2 = sortList(slow.next, tail);
        slow.next = null;
        return mergeSort(l1, l2);
    }


    //给两个有序链表排序
    private ListNode mergeSort(ListNode l1, ListNode l2) {
        ListNode head;
        if (l1 == null || l2 == null) {
            head = l1 == null ? l2 : l1;
            return head;
        }
        if (l1.val < l2.val) {
            head = l1;
            head.next = mergeSort(l1.next, l2);
        } else {
            head = l2;
            head.next = mergeSort(l1, l2.next);
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(4);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(3);
        head.next.next.next.next = new ListNode(5);
        SortList sortList = new SortList();
        ListNode sortedList = sortList.sortList(head);
        while (sortedList != null) {
            System.out.println(sortedList.val);
            sortedList = sortedList.next;
        }
    }
}
